Da iteração para a recursão: a reconstrução do pensamento
A recursão (Recursion) é uma abordagem que fundamentalmente altera a perspectiva de resolução de problemas. Ao lidar com problemas como a soma de listas,método iterativo(Listagem de Código 4-2) depende de um acumulador explícito theSum e controle de estado do ciclo; enquanto o método recursivo depende de uma definição matemática profunda:
$$listsum(numList) = first(numList) + listsum(rest(numList))$$
A recursão não é apenas uma função chamando a si mesma; ela divide um problema complexo em subproblemas de menor escala com a mesma estrutura, cujo cerne está na identificação daauto-similaridade。递归执行包含两个对称阶段：
- fase "descida": cortando continuamente a lista e empilhando as chamadas até alcançar o caso-basecaso-base(Caso Base).
- fase "retorno": começando do estado mais simples, retornando progressivamente e combinando os resultados.
Intuição central
O pensamento iterativo é como pegar um balde e ir colocando números um por um para somá-los; já o pensamento recursivo é como dizer: 'Se você me disser qual é a soma dos números restantes, eu só preciso adicionar o primeiro número.'